Memory caches are storage systems incorporated into data processing systems for performance reasons. A memory cache stores a subset of the contents of the data processing system's main memory for use by a selected subsystem, typically the system's data processor. A memory cache can supply data to the data processor faster than the main memory can because of several reasons. First, the memory cache is often made of higher grade memory circuits than is the main memory system. These circuits can simply operate at a higher clock rate than can the main memory. Also, there may be a dedicated bus between the data processor and the memory cache that results in higher bandwidth between the data processor and the memory cache than between the data processor and the main memory. Finally, a memory cache may be physically located on the same integrated circuit as the subsystem to which it provides data. In this case, the memory cache is constructed from faster circuits and there is a dedicated bus between the memory cache and the data processor.
Associativity is one variable that defines memory cache designs. Associativity describes the number of memory cache locations to which each main memory subsystem location may be mapped. For instance, the contents of each main memory location may be mapped to one of two different locations in a two-way set associative memory cache. When the data processor requests the contents of a certain main memory location, the data processor compares the contents of a tag associated with each of the two possible storage locations to a portion of the address of the requested data. The tag is stored in a random access memory ("RAM") associated with each memory cache entry or "cache line." One or none of the tags will match the address portion depending upon the prior history of the data processor. If one of the tags matches, then the associated memory cache location contains the requested data, a cache "hit." If neither of the tags matches, then no memory cache location contains the requested data, a cache "miss."
Indexing and tagging are other variables that define memory cache designs. Indexing describes what type of address the data processor uses to select entries in the memory cache. Tagging describes what type of address generated the tag associated with each entry in the cache line. Generally, data processing systems use at least two types of addresses. The data processor typically calculates addresses for purposes of fetching instructions in a first address format. These addresses are often called "effective" addresses. The main memory subsystem typically stores data according to a second addressing format. These addresses are often called "real" or "physical" addresses. A data processor in such a dual-addressing system contains translation tables to map addresses between the two formats.
Semi-associative caches are high performance cache memory systems. Semi-associative caches use content addressable memories ("CAMs") to narrow down the identity of the desired cache line to a single cache line before the real address is known. The validity of the data associated with the single cache line is determined by comparing its real address tag to the effective address translated by a translation array. No multiplexer stage is required to select one of N outputs, where N is the set associative way of the semi-associative cache. As described below, semi-associative caches are able to maintain the advantage of N-way associativity.
A CAM tag and a RAM tag are associated with each cache line in a semi-associative cache. The CAM stores a subset of the effective address of the cache line ("E-tag") and the RAM stores a subset of the real address of the cache line ("R-tag"). When the data processor needs a particular cache line, it binarily indexes into a certain number of cache lines with a first subset of the effective address and matches a second subset of the effective address against the contents of the CAMs in the certain number of cache lines. The certain number of cache lines is referred to as a "camlet." The number of entries in the camlet determines the way associativity of the memory cache. One or none of the CAMs in a particular camlet may match the second subset of the effective address. A match indicates that the requested data may be in the cache line associated with the matching CAM, an E-tag hit. The effective address must be translated into a real address and the real address compared to the R-tag of the matching cache line to determine if a full cache hit is appropriate.
Semi-associative caches suffer a problem known as "cache aliasing." Known solutions to cache aliasing themselves suffer several disadvantages. Cache aliasing occurs when two or more entries in a camlet have the same E-tag. This problem is especially acute after a memory cache request resulting in an E-tag hit and an R-tag miss. In this case, the memory cache must fetch data from main memory that will have, by definition, the same E-tag as the half-matching cache line. If the memory cache places this data directly into another cache line in the same camlet, then a cache alias will occur. The next request for this new data or for the data associated with the half-match will cause two CAMs to match and output their cache lines and R-tags. The memory cache will not operate properly if a cache alias OCCURS.
Prior solutions to cache aliasing required that a cache line immediately be invalidated after it generated the combination of an E-tag hit and an R-tag miss. This solution does preclude two camlet entries from ever having the same E-tag. However, this invalidated cache line may be useful to the data processor while the memory cache is fetching the previously requested cache line. The memory cache will be busy for one clock cycle during the invalidation step. This cycle might otherwise be used for other accesses to the memory cache. Also, this solution leads to added cache control logic complexity.